package fr.cdesire.sudoku.core;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedSet;

import fr.cdesire.sudoku.core.commons.Case;
import fr.cdesire.sudoku.core.commons.Grille;
import fr.cdesire.sudoku.core.commons.Position;
import fr.cdesire.sudoku.core.enums.Valeur;
import fr.cdesire.sudoku.core.exceptions.GrillePlusieursSolutionsException;
import fr.cdesire.sudoku.core.exceptions.GrilleSansSolutionsException;
import fr.cdesire.sudoku.core.exceptions.SudokuCoreException;

/**
 * Cette classe permet de trouver la solution d'une grille Sudoku quand 
 * celle-ci est possible.
 * 
 * @author cedric.desire@gmail.com
 */
public class Recherche {

    /**
     * Constructeur privé.
     */
    private Recherche() {
        super();
    }

    /**
     * Recherche une solution à la grille.
     *
     * @param grille Grille initiale de départ pour la recherche.
     * @return Solution de la grille.
     * @throws SudokuCoreException Exception de type GrilleSansSolutionsException levée quand
     * aucune solution existante. Exception de type GrillePlusieursSolutionsException quand 
     * il existe plus d'une solution trouvée.
     */
    protected static Grille rechercheSolution(Grille grille) throws SudokuCoreException {

        Deque<Grille> solutionsPossibles = new ArrayDeque<Grille>();
        Set<Grille> solutionsTrouvees = new HashSet<Grille>();

        for (Position position : grille.getValeursRenseignees().keySet()) {
            setValeur(grille, position, grille.getValeursRenseignees().get(position));
        }

        solutionsPossibles.addFirst(grille);
        while (!solutionsPossibles.isEmpty() && solutionsTrouvees.size() < 2) {
            chercheSolution(solutionsPossibles.removeFirst(), solutionsPossibles, solutionsTrouvees);
        }

        if (solutionsTrouvees.isEmpty()) {
            throw new GrilleSansSolutionsException();
        }

        if (solutionsTrouvees.size() == 2) {
            Iterator<Grille> solutionsIterator = solutionsTrouvees.iterator();
            throw new GrillePlusieursSolutionsException(solutionsIterator.next(), solutionsIterator.next());
        }

        return solutionsTrouvees.iterator().next();
    }

    /**
     * Recherche de la solution à partir d'un état de la grille. Soit cet état est une/la 
     * solution à la grille, soit cet état conduit à création de nouveaux états de la 
     * grille : un pour chaque possibilité de la case ayant le moins de possibilités, 
     * soit cet état est une grille invalide.
     * @param grille Etat de la grille.
     */
    private static void chercheSolution(Grille grille, Deque<Grille> solutionsPossibles, Set<Grille> solutionsTrouvees) {

        SortedSet<Case> casesVides = grille.getCasesVidesTriees();

        if (casesVides.isEmpty()) {
            solutionsTrouvees.add(grille);
            return;
        }

        Case premiereCase = casesVides.first();
        Iterator<Valeur> iteValeurs = casesVides.first().getValeurs().iterator();

        while (iteValeurs.hasNext()) {

            Valeur valeur = iteValeurs.next();
            Grille grilleClone = grille.duplicate();

            try {
                setValeur(grilleClone, premiereCase.getPosition(), valeur);
                solutionsPossibles.addFirst(grilleClone);
            } catch (SudokuCoreException e) {
                // Etat de la grille invalide : On ne fait rien.
            }
        }
    }

    /**
     * Fixe une valeur unique sur une case et retire cette valeur des cases dépendantes à celle-ci.
     * Cette méthode est appelée récursivement sur les cases dépendantes pour lesquelles il ne reste
     * alors plus qu'une valeur disponible.
     * @param grille Etat de la grille sur laquelle la valeur de la case doit-être fixé.
     * @param position Position de la case.
     * @param valeur Valeur de la case.
     * @throws SudokuCoreException Lève une GrilleSansSolutionException quand l'état de
     * la grille n'est pas valide.
     */
    private static void setValeur(Grille grille, Position position, Valeur valeur) throws SudokuCoreException {

        Case caseARemplir = grille.getCases().get(position);
        caseARemplir.getValeurs().clear();
        caseARemplir.getValeurs().add(valeur);

        setValeur(grille, caseARemplir);
    }

    /**
     * Retire la valeur de la case remplie aux cases dépendantes.
     * Cette méthode est appelée récursivement sur les cases dépendantes pour lesquelles il ne reste
     * alors plus qu'une valeur disponible.
     * @param grille Etat de la grille.
     * @param caseRemplie Case sur laquelle une valeur a été fixée.
     * @throws SudokuCoreException Lève une GrilleSansSolutionException qand l'état de
     * la grille n'est pas valide.
     */
    private static void setValeur(Grille grille, Case caseRemplie) throws SudokuCoreException {

        Valeur valeurRemplie = caseRemplie.getValeur();

        Set<Position> positionsImpactees = grille.getFormatGrille().getPositionsDependantes().get(caseRemplie.getPosition());

        for (Position positionImpactee : positionsImpactees) {

            Case caseImpactee = grille.getCases().get(positionImpactee);

            if (caseImpactee.isCaseVide()) {
                caseImpactee.getValeurs().remove(valeurRemplie);
                Valeur valeurImpactee = caseImpactee.getValeur();

                if (valeurImpactee != null) {
                    setValeur(grille, caseImpactee);
                }

                // La grille est invalide si la case impactée et la case remplie partagent la même valeur.
            } else if (valeurRemplie.equals(caseImpactee.getValeur())) {
                throw new GrilleSansSolutionsException();
            }
        }
    }
}
